Problem | DSA

Reverse a Linked List — Real Interview Walkthrough

You walk into the interview room. After a quick greeting, the interviewer smiles — “Alright, let’s start with something classic.”

Interviewer: Can you reverse a linked list?

Candidate: Sure, but just to confirm — are we talking about a singly linked list or a doubly linked one? And do we have permission to modify it in place?

Interviewer: Great clarifying questions. It’s a singly linked list, and yes — you can modify it in place. Let’s hear your thought process.

Step 1: Understanding the Problem

We’re given the head of a singly linked list. We need to reverse the links between nodes so that the head becomes the tail and the tail becomes the head.

Example:

Input: 1 → 2 → 3 → 4 → 5
Output: 5 → 4 → 3 → 2 → 1

Goal: Change the direction of links, not the node values.

Step 2: Thinking Aloud (Iterative Approach)

Candidate: Okay, I’ll start with the iterative solution — it’s usually the most memory-efficient.

Imagine standing at each node one by one and flipping its arrow (the next pointer) backward. But to avoid losing track of the next node, we’ll keep three pointers: prev, curr, and nextNode.

function reverseLinkedList(head):
    # Initialize previous pointer as null
    prev = null
    curr = head

    # Traverse until the end of the list
    while curr is not null:
        nextNode = curr.next      # Temporarily store next node
        curr.next = prev          # Reverse the current link
        prev = curr               # Move prev forward
        curr = nextNode          # Move curr forward

    # After the loop, prev is the new head
    return prev

Time Complexity: O(n) — we visit each node once.
Space Complexity: O(1) — only a few variables used.

Interviewer: Can you explain what happens when curr becomes null?

Candidate: That means we’ve reached the end of the list. At that moment, prev points to the new head of the reversed list, so we simply return it.

Step 3: Alternate Thought (Recursive Approach)

Interviewer: Nice! Can you also explain how you’d do this recursively?

Candidate: Sure! Recursion naturally reverses the list because it dives to the end first, then connects nodes in reverse order as the calls return back up.

function reverseList(head):
    # Base case: empty list or single node
    if head is null or head.next is null:
        return head

    # Reverse the rest of the list first
    newHead = reverseList(head.next)

    # Fix the current node’s link
    head.next.next = head
    head.next = null

    return newHead

Time Complexity: O(n)
Space Complexity: O(n) — recursion stack depth.

Step 4: Deeper Understanding

Interviewer: Between the two, which approach would you choose in real-world code?

Candidate: The iterative approach. It’s more memory-efficient since recursion adds call stack overhead. But for clarity or conceptual explanation, recursion beautifully shows the reversal flow.

Interviewers often test this question not for code, but for how you explain pointer manipulation step by step — that’s where many candidates trip up.

Key Takeaways

Always clarify assumptions — shows real-world problem thinking.
Iterative reversal → O(n) time, O(1) space.
Recursive reversal → intuitive but O(n) stack.
Explain pointer movement — that’s what interviewers value most.

This “simple” question often decides whether you can explain clearly under pressure. Don’t rush to code — narrate your thought process like a story.